# -*- coding: utf-8 -*-
"""
二分查找,时间复杂度为O(logN)
"""

def binary_search(data, target, low, high):
    """Return True if target is found in indicated portion of a Python list.

    The search only considers the portion from data[low] to data[high] inclusive.
    """
    if low > high:
        return False
    mid = low + (high - low) // 2
    if data[mid] == target:
        return True
    elif data[mid] < target:
        return binary_search(data, target, mid + 1, high)
    else:
        return binary_search(data, target, low, mid - 1)


if __name__ == "__main__":
    data_list = [3,4,9,12,19,28]
    print(binary_search(data_list,4,0,len(data_list)-1))
    print(binary_search(data_list,14,0,len(data_list)-1))
